# -*- coding: utf-8 -*- 
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/9/30
# @File : 18.Increasing SubsequenceⅡ.py
# dp+二分优化 nlogn做法，正常人都很难想出来。
# 如果要使上升子序列尽可能的长，那么就要让序列上升得尽可能慢.这样后续会有更多的机会得到一个更长的子序列,子序列继续变长的''潜力''增大了。 如果子序列长度相同，则终点越小，则后面增长的潜能就越大，所以，将长度相同的位置（每个i）设成其中最小值

def dp_solve(cnt):
    for i in range(1,n):
        if a[i] > dp[cnt-1]:#如果遍历到的a[i]比dp数组的最大值也就是最后一位还要大，说明后一个位置也可以是最长子序列的末位，所以直接append到dp的后面
            dp.append(a[i])
            cnt += 1
        else:#如果遍历到的a[i]比dp数组的最大值要小，则在dp中找到不小于a[i]的最小值的位置，用a[i]的替换dp数组这个位置的值。
            l = -1
            r = cnt
            while (l + 1 < r):#二分模板 求不小于a[i]的最小值
                mid = (l + r) // 2
                if dp[mid] >= a[i]:
                    r = mid
                else:
                    l = mid
            dp[r] = a[i]
    return cnt# 最终返回dp数组的长度

"""
dp[i]代表长度为i+1最长子序列的最后一个数最小可以是多少，dp数组是严格递增的
"""
if __name__ == '__main__':
    n = int(input())
    a = [int(i) for i in input().split()]
    dp = [a[0]]
    cnt = 1
    ans = dp_solve(cnt)
    print(ans)